<!DOCTYPE html>












  


<html class="theme-next mist use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">






  
  
    
    
  <script src="/lib/pace/pace.min.js?v=1.0.2"></script>
  <link href="/lib/pace/pace-theme-center-atom.min.css?v=1.0.2" rel="stylesheet">







<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />



















  
  
  
  

  

  

  

  

  

  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=6.3.0" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.3.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=6.3.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=6.3.0">


  <link rel="mask-icon" href="/images/logo.svg?v=6.3.0" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    version: '6.3.0',
    sidebar: {"position":"left","width":260,"display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":true},
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="专业课复习纲要">
<meta name="keywords" content="2019考研">
<meta property="og:type" content="article">
<meta property="og:title" content="计算机专业课复习纲要">
<meta property="og:url" content="https://flamywhale.github.io/2018/11/29/cs-course-outline/index.html">
<meta property="og:site_name" content="The Island">
<meta property="og:description" content="专业课复习纲要">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://flamywhale.github.io/images/201811/cpu_inititalization.png">
<meta property="og:updated_time" content="2018-12-18T00:33:24.226Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="计算机专业课复习纲要">
<meta name="twitter:description" content="专业课复习纲要">
<meta name="twitter:image" content="https://flamywhale.github.io/images/201811/cpu_inititalization.png">






  <link rel="canonical" href="https://flamywhale.github.io/2018/11/29/cs-course-outline/"/>



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>计算机专业课复习纲要 | The Island</title>
  









  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">The Island</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <p class="site-subtitle">Created at 2018</p>
      
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">
    <a href="/categories/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-th"></i> <br />分类</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/tags/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />标签</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-about">
    <a href="/about/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于</a>
  </li>

      
      
    </ul>
  

  
    

  

  
</nav>



  



</div>
    </header>

    
  
  
  
    
      
    
    <a href="https://github.com/flamywhale" class="github-corner" target="_blank" title="Follow me on GitHub" aria-label="Follow me on GitHub"><svg width="80" height="80" viewBox="0 0 250 250" style="fill:#222; color:#fff; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg>
    
      </a>
    



    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  
    <div class="reading-progress-bar"></div>
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://flamywhale.github.io/2018/11/29/cs-course-outline/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Wu Jiahao ♡">
      <meta itemprop="description" content="Stay hungry, stay foolish.">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="The Island">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">计算机专业课复习纲要
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-11-29 00:00:00" itemprop="dateCreated datePublished" datetime="2018-11-29T00:00:00+08:00">2018-11-29</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2018-12-18 08:33:24" itemprop="dateModified" datetime="2018-12-18T08:33:24+08:00">2018-12-18</time>
              
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/2018年11月/" itemprop="url" rel="index"><span itemprop="name">2018年11月</span></a></span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          
              <div class="post-description">专业课复习纲要</div>
          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h2><ul>
<li><a href="#数据结构">数据结构</a><ul>
<li><a href="#数据结构考试要求">数据结构考试要求</a></li>
<li><a href="#绪论">绪论</a></li>
<li><a href="#线性表">线性表</a></li>
<li><a href="#堆栈与队列">堆栈与队列</a></li>
<li><a href="#数组和广义表">数组和广义表</a></li>
<li><a href="#树与二叉树">树与二叉树</a></li>
<li><a href="#图">图</a><ul>
<li><a href="#关键路径">关键路径</a></li>
</ul>
</li>
<li><a href="#查找">查找</a></li>
<li><a href="#排序">排序</a></li>
</ul>
</li>
<li><a href="#操作系统">操作系统</a><ul>
<li><a href="#操作系统考试要求">操作系统考试要求</a></li>
<li><a href="#操作系统概述">操作系统概述</a></li>
<li><a href="#进程">进程</a></li>
<li><a href="#线程对称多处理smp和微内核">线程、对称多处理smp和微内核</a></li>
<li><a href="#处理器调度">处理器调度</a></li>
<li><a href="#并发性">并发性</a></li>
<li><a href="#软件实现互斥小结">软件实现互斥小结</a></li>
<li><a href="#管程小结">管程小结</a></li>
<li><a href="#生产者消费者问题">生产者消费者问题</a></li>
<li><a href="#存储器管理">存储器管理</a><ul>
<li><a href="#分区管理方式小结">分区管理方式小结</a></li>
</ul>
</li>
<li><a href="#设备管理和磁盘调度">设备管理和磁盘调度</a></li>
<li><a href="#文件系统">文件系统</a><ul>
<li><a href="#外存分配方式小结">外存分配方式小结</a></li>
</ul>
</li>
<li><a href="#分布式系统">分布式系统</a></li>
<li><a href="#操作系统安全">操作系统安全</a></li>
</ul>
</li>
<li><a href="#计算机体系结构">计算机体系结构</a><ul>
<li><a href="#计算机体系结构部分考试要求">计算机体系结构部分考试要求</a><ul>
<li><a href="#基于mips处理器的linux操作系统tlb例外过程">基于MIPS处理器的Linux操作系统TLB例外过程</a></li>
<li><a href="#io通信中dma传输过程">I/O通信中DMA传输过程</a></li>
<li><a href="#系统初始化时pci设备的探测过程">系统初始化时PCI设备的探测过程</a></li>
<li><a href="#先行进位加法器结构及其verilog实现">先行进位加法器结构及其verilog实现</a></li>
</ul>
</li>
<li><a href="#计算机体系结构概论">计算机体系结构概论</a></li>
<li><a href="#指令系统结构">指令系统结构</a><ul>
<li><a href="#指令系统的演变">指令系统的演变</a></li>
<li><a href="#指令集结构">指令集结构</a></li>
<li><a href="#异常与中断">异常与中断</a></li>
<li><a href="#存储管理">存储管理</a></li>
</ul>
</li>
<li><a href="#计算机硬件结构">计算机硬件结构</a><ul>
<li><a href="#系统复位到操作系统启动的简要流程图">系统复位到操作系统启动的简要流程图</a></li>
<li><a href="#设备探测及驱动加载">设备探测及驱动加载</a></li>
</ul>
</li>
<li><a href="#cpu微结构">cpu微结构</a></li>
</ul>
</li>
</ul>
<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><h3 id="数据结构考试要求"><a href="#数据结构考试要求" class="headerlink" title="数据结构考试要求"></a>数据结构考试要求</h3><ul>
<li style="list-style: none"><input type="checkbox"> 掌握数据结构的基本概念、基本原理和基本方法。</li>
<li style="list-style: none"><input type="checkbox"> 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。</li>
<li style="list-style: none"><input type="checkbox"> 能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。</li>
</ul>
<h3 id="绪论"><a href="#绪论" class="headerlink" title="绪论"></a>绪论</h3><ol>
<li>数据结构的基本概念，数据的逻辑结构、存储结构。<ul>
<li>逻辑结构：非线性结构、线性结构</li>
<li>存储结构：顺序、链式、索引、散列</li>
</ul>
</li>
<li>算法的定义、算法的基本特性以及算法分析的基本概念。</li>
</ol>
<h3 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h3><ol>
<li>线性表的定义、基本操作。</li>
<li>线性表的实现及应用，包括顺序存储结构、链式存储结构（单链表、循环链表和双向链表）的构造原理，在两种存储结构上对线性表实施的主要的操作（三种链表的建立、插入和删除、检索等）的算法设计与实现。</li>
</ol>
<h3 id="堆栈与队列"><a href="#堆栈与队列" class="headerlink" title="堆栈与队列"></a>堆栈与队列</h3><ol>
<li>堆栈与队列的基本概念、基本操作。</li>
<li>堆栈与队列的顺序存储结构、链式存储结构的构造原理。</li>
<li>在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现。</li>
</ol>
<h3 id="数组和广义表"><a href="#数组和广义表" class="headerlink" title="数组和广义表"></a>数组和广义表</h3><ol>
<li>数组的基本概念、多维数组的实现。</li>
<li>对称矩阵和稀疏矩阵的压缩存储。</li>
<li>广义表的基本概念。</li>
</ol>
<h3 id="树与二叉树"><a href="#树与二叉树" class="headerlink" title="树与二叉树"></a>树与二叉树</h3><ol>
<li>树的基本概念和性质。<ol>
<li>树中的结点数等于所有结点的度数+1</li>
</ol>
</li>
<li>二叉树的基本概念、性质。</li>
<li>二叉树的存储，包括顺序存储、链式存储结构。</li>
<li>二叉树的遍历。</li>
<li>线索二叉树的基本概念和构造。</li>
<li>树和森林的存储结构、遍历。</li>
<li>哈夫曼（Huffman）树和哈夫曼编码?。</li>
</ol>
<h3 id="图"><a href="#图" class="headerlink" title="图"></a>图</h3><ol>
<li>图的基本概念和性质。</li>
<li>图的存储，包括邻接矩阵法、邻接表法。</li>
<li>图的遍历操作，包括深度优先搜索、广度优先搜索。</li>
<li>最小生成树、最短路径、关键路径、拓扑排序算法的原理、实现和应用。</li>
</ol>
<h4 id="关键路径"><a href="#关键路径" class="headerlink" title="关键路径"></a>关键路径</h4><table>
<thead>
<tr>
<th style="text-align:left">算法流程</th>
<th style="text-align:left">解释</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left">事件（顶点）的 ve</td>
<td style="text-align:left">源点到该点的最长路径长度； ve(源点) = 0</td>
</tr>
<tr>
<td style="text-align:left">事件（顶点）的 vl</td>
<td style="text-align:left">从汇点开始计算，$ vl(k) = [ vl(j) - weight(k,j)]_{min}$；vl(汇点) = ve(汇点)</td>
</tr>
<tr>
<td style="text-align:left">活动（边）的 e</td>
<td style="text-align:left">边的起点的 ve</td>
</tr>
<tr>
<td style="text-align:left">活动（边）的 l</td>
<td style="text-align:left">边的终点的 vl $-$ 边的权重</td>
</tr>
<tr>
<td style="text-align:left">活动（边）的 l-e</td>
<td style="text-align:left">$l - e = 0$ 的边就是关键路径</td>
</tr>
</tbody>
</table>
<h3 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h3><ol>
<li>顺序查找法、分块查找法、折半查找方法的原理、实现和应用。</li>
<li>二叉排序树、平衡二叉树、键树的原理、实现和应用。</li>
<li>B树及其基本操作、B+树的基本概念。<ul>
<li>B树的查找、插入、删除操作</li>
<li>B树是一种平衡的多路查找树，是为了磁盘或其它存储设备而设计的一种多叉树。</li>
<li>B+树在关系型数据库中使用，可以顺序查找。</li>
</ul>
</li>
<li>哈希（Hash）表的原理、实现和应用。</li>
<li>字符串模式匹配算法的原理和实现。<ul>
<li>KMP算法<ul>
<li>求数组 <code>next[]</code> 的值</li>
</ul>
</li>
</ul>
</li>
</ol>
<h3 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h3><ol>
<li>排序的基本概念。</li>
<li>排序的原理、实现和复杂度<ul>
<li style="list-style: none"><input type="checkbox" checked> 直接插入排序</li>
<li style="list-style: none"><input type="checkbox" checked> 折半插入排序</li>
<li style="list-style: none"><input type="checkbox" checked> 气泡排序</li>
<li style="list-style: none"><input type="checkbox" checked> 快速排序</li>
<li style="list-style: none"><input type="checkbox" checked> 简单选择排序</li>
<li style="list-style: none"><input type="checkbox" checked> 堆排序</li>
<li style="list-style: none"><input type="checkbox" checked> 二路归并排序</li>
<li style="list-style: none"><input type="checkbox" checked> 基数排序</li>
<li style="list-style: none"><input type="checkbox" checked> 外部排序算法 （!?!）<ul>
<li style="list-style: none"><input type="checkbox" checked> 多路平衡归并与败者树 （?）</li>
<li style="list-style: none"><input type="checkbox" checked> 置换 - 选择排序（生成初始归并段）与最佳归并树</li>
</ul>
</li>
</ul>
</li>
<li>排序算法的应用。</li>
</ol>
<h2 id="操作系统"><a href="#操作系统" class="headerlink" title="操作系统"></a>操作系统</h2><h3 id="操作系统考试要求"><a href="#操作系统考试要求" class="headerlink" title="操作系统考试要求"></a>操作系统考试要求</h3><ul>
<li style="list-style: none"><input type="checkbox"> 了解操作系统所管辖的软、硬件资源；了解操作系统的关键概念，从整体上把握操作系统的特性与功能等概念；建立操作系统的资源管理和应用接口的职能概念。理解系统调用的执行过程。</li>
<li style="list-style: none"><input type="checkbox"> 掌握进程的本质特征，明确进程的<strong>动态特性</strong>，理解进程的地址空间分布，熟悉进程状态间转换的原因，建立进程是资源分配单元和一种运行实体的基本理念。</li>
<li style="list-style: none"><input type="checkbox"> 理解引入线程作为基本运行实体的必要性和可能性；掌握线程各种实现方式及其特点；熟悉 SMP 体系结构、操作系统的体系结构。</li>
<li style="list-style: none"><input type="checkbox"> 了解批处理、交互式、实时三种调度类型；重点掌握进程调度的各种算法及其适用环了解实时进程的本质，掌握限期调度和速率单调调度方法。</li>
<li style="list-style: none"><input type="checkbox"> 灵活运用信号量、管程等技术解决互斥合同步问题；理解死锁的概念和产生死锁的充分必要条件；熟练掌握死锁的预防、避免和检测算法；了解处理死锁问题时避免饥饿的方法。</li>
<li style="list-style: none"><input type="checkbox"> 理解存储管理的功能及存储管理对多道程序设计的支持；掌握段、页式存储管理方法及实现技术；掌握虚存的原理及相关的各种替换算法和数据结构。</li>
<li style="list-style: none"><input type="checkbox"> 理解输入输出设备及操作系统中输入/输出功能的组织、掌握中断处理、设备驱动程序、设备无关的软件接口和 spooling 等技术，重点掌握各种用于提高性能的缓冲策略和磁盘调度算法；了解可提高性能和可靠性的各种磁盘阵列配置方式。</li>
<li style="list-style: none"><input type="checkbox"> 理解文件系统特点与文件组织，掌握文件系统的基本数据结构，了解文件、目录的基本性质及其实现方法；重点掌握磁盘空间的管理、文件系统的性能及可靠性、文件系统的安全性及保护机制，分布式文件系统的问题和特点等。</li>
<li style="list-style: none"><input type="checkbox"> 了解分布式处理的特点、类型；掌握多层体系结构和机群系统的基本概念和特点。</li>
<li style="list-style: none"><input type="checkbox"> 了解操作系统安全保密性、完整性和可用性的基本概念及保护方法。了解常用的攻击和防御技术的原理。</li>
</ul>
<h3 id="操作系统概述"><a href="#操作系统概述" class="headerlink" title="操作系统概述"></a>操作系统概述</h3><ol>
<li>计算机基本构成、处理器的内部结构、高速缓冲存储器 <code>cache</code></li>
<li>操作系统的概念、演变历程、特性、分类、运行环境、功能</li>
<li>系统调用的功能和过程。</li>
</ol>
<h3 id="进程"><a href="#进程" class="headerlink" title="进程"></a>进程</h3><ol>
<li>进程、进程描述、进程地址空间分布及进程状态转换</li>
</ol>
<h3 id="线程、对称多处理smp和微内核"><a href="#线程、对称多处理smp和微内核" class="headerlink" title="线程、对称多处理smp和微内核"></a>线程、对称多处理smp和微内核</h3><ol>
<li>线程的概念，定义线程的必要性和可能性；</li>
<li>线程的功能特性与实现方式；<ol>
<li>线程是<strong>独立调度</strong>的基本单位</li>
<li><strong>用户级线程</strong>和<strong>内核线程</strong></li>
</ol>
</li>
<li>操作系统的体系结构（微内核与巨内核）及其性能分析。<ol>
<li>巨内核：主要功能模块运行在内核，模块之间联系紧密，性能很好；但是难以维护，没法提供层次清晰的接口。</li>
<li>微内核：基本功能保存在内核，其他模块运行在用户态；能够提供层次清晰的接口，便于维护操作系统，推进操作系统的演进，但增大了开销。</li>
</ol>
</li>
</ol>
<h3 id="处理器调度"><a href="#处理器调度" class="headerlink" title="处理器调度"></a>处理器调度</h3><ol>
<li>处理器的三种调度类型；<ul>
<li>作业调度：为程序建立进程；</li>
<li>中级调度：为了调高内存利用率，暂时挂起不工作的进程；</li>
<li>进程调度</li>
</ul>
</li>
<li>进程调度的各种算法及其特点<ul>
<li>FCFS（先来先服务）</li>
<li>SJF（最短时间优先）</li>
<li>最短剩余时间优先</li>
<li>优先级调度</li>
<li>高响应比优先调度 ($R_p = \dfrac{t_{wait} + t_{serve}}{t_{serve}}$)</li>
<li>RR - Round Robin（时间片轮转）</li>
<li>VRR （虚拟轮转调度）<ul>
<li>添加 <code>I/O</code> 进程的辅助 <code>FIFO</code> 队列， 辅助队列优先级高</li>
<li>对 <code>I/O</code> 密集型进程友好</li>
</ul>
</li>
<li>多级反馈队列</li>
<li>公平共享调度</li>
<li>彩票调度</li>
</ul>
</li>
<li>多处理器对进程调度的影响</li>
<li>实时进程的特点，限期调度和速率单调调度方法。</li>
</ol>
<h3 id="并发性"><a href="#并发性" class="headerlink" title="并发性"></a>并发性</h3><ol>
<li>并发性问题及相关概念，如临界区、互斥、信号量和管程等；<ul>
<li>管程<ul>
<li>由一组数据及定义在这组数据上的对这组数据的操作组成的软件模块。</li>
</ul>
</li>
<li>互斥<ul>
<li>原则：忙则等待、空闲则进、有限等待、让权等待</li>
<li>基本方法：<ul>
<li>软件实现<ul>
<li>单标志法（违背“空闲则进”原则）</li>
<li>双标志法先检查（违背“忙则等待”原则）</li>
<li>双标志法后检查（会导致“饥饿”现象）</li>
<li>皮特森法（单标志+双标志法后检查）</li>
</ul>
</li>
<li>硬件实现：中断屏蔽法、硬件指令法</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>进程互斥、同步和通信的各种算法；<ul>
<li>生产-消费问题</li>
<li>哲学家吃饭问题</li>
</ul>
</li>
<li>死锁的概念、死锁的原因和条件<ul>
<li>概念<ul>
<li>多个进程因为竞争系统资源而造成的互相等待的僵局</li>
</ul>
</li>
<li>原因<ul>
<li>竞争资源</li>
<li>进程推进顺序非法</li>
</ul>
</li>
<li>条件<ul>
<li>互斥条件</li>
<li>不剥夺条件</li>
<li>请求和保持条件</li>
<li>环路等待条件</li>
</ul>
</li>
</ul>
</li>
<li>死锁的预防、避免和检测算法。<ul>
<li>预防<ul>
<li>资源的有序分配（破坏死锁的<strong>循环等待</strong>条件）</li>
</ul>
</li>
<li>避免<ul>
<li>核心是关注系统的<strong>安全状态</strong>（是否存在进程能够正常运行的顺序）</li>
<li>银行家算法</li>
</ul>
</li>
<li>检测<ul>
<li>死锁定理：S 为死锁 $\Leftrightarrow$ S 状态的资源分配图不可简化</li>
<li>资源剥夺法（挂起某些死锁进程，将其资源分配给其他死锁进程）</li>
<li>撤销进程法（撤销部分或者全部死锁进程）</li>
</ul>
</li>
</ul>
</li>
</ol>
<h4 id="软件实现互斥小结"><a href="#软件实现互斥小结" class="headerlink" title="软件实现互斥小结"></a>软件实现互斥小结</h4><ol>
<li><p>单标志法</p>
 <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> turn;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_i</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (turn != i);</span><br><span class="line">    critical section;</span><br><span class="line">    turn = j;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_j</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (turn != j);</span><br><span class="line">    critical section;</span><br><span class="line">    turn = i;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>双标志先检查</p>
 <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_i</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (flag[j]);</span><br><span class="line">    flag[i] = TRUE;</span><br><span class="line">    critical section;</span><br><span class="line">    flag[i] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_j</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (flag[i]);</span><br><span class="line">    flag[j] = TRUE;</span><br><span class="line">    critical section;</span><br><span class="line">    flag[j] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>双标志后检查</p>
 <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_i</span><span class="params">()</span></span>&#123;</span><br><span class="line">    flag[i] = TRUE;</span><br><span class="line">    <span class="keyword">while</span> (flag[j]);</span><br><span class="line">    critical section;</span><br><span class="line">    flag[i] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_j</span><span class="params">()</span></span>&#123;</span><br><span class="line">    flag[j] = TRUE;</span><br><span class="line">    <span class="keyword">while</span> (flag[i]);</span><br><span class="line">    critical section;</span><br><span class="line">    flag[j] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>Peterson 算法</p>
 <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_i</span><span class="params">()</span></span>&#123;</span><br><span class="line">    flag[i] = TRUE; turn = j;</span><br><span class="line">    <span class="keyword">while</span> (flag[j] &amp;&amp; (turn == j));</span><br><span class="line">    critical section;</span><br><span class="line">    flag[i] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P_j</span><span class="params">()</span></span>&#123;</span><br><span class="line">    flag[i] = TRUE; turn = i;</span><br><span class="line">    <span class="keyword">while</span> (flag[j] &amp;&amp; (turn == i));</span><br><span class="line">    critical section;</span><br><span class="line">    flag[j] = FALSE;</span><br><span class="line">    remainder section;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>
<h4 id="管程小结"><a href="#管程小结" class="headerlink" title="管程小结"></a>管程小结</h4><p>使用管程实现生产者-消费者问题。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 条件变量实现</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Condition</span>&#123;</span></span><br><span class="line">    <span class="comment">// variables</span></span><br><span class="line">    <span class="keyword">int</span> numWaiting;</span><br><span class="line">    Waitqueue q;</span><br><span class="line">    <span class="comment">// functions</span></span><br><span class="line">    Condition() &#123;</span><br><span class="line">        numWaiting = <span class="number">0</span>;</span><br><span class="line">        q = <span class="keyword">new</span> Waitqueue();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// wait function</span></span><br><span class="line">    wait(Lock &amp;lock) &#123;</span><br><span class="line">        numWaiting++;</span><br><span class="line">        Add <span class="keyword">this</span> thread t to q;</span><br><span class="line">        release(lock);</span><br><span class="line">        schedule(); <span class="comment">//need mutex</span></span><br><span class="line">        acquire(lock);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// signal function</span></span><br><span class="line">    signal() &#123;</span><br><span class="line">        <span class="keyword">if</span> (numWaiting &gt; <span class="number">0</span>)&#123;</span><br><span class="line">            Remove a thread t from q;</span><br><span class="line">            wakeup(t); <span class="comment">//need mutex</span></span><br><span class="line">            numWaiting--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 管程类实现</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BoundedBuffer</span> &#123;</span></span><br><span class="line">    <span class="comment">// variables</span></span><br><span class="line">    ...</span><br><span class="line">    Lock *lock;</span><br><span class="line">    <span class="keyword">int</span> count;</span><br><span class="line">    Condition notFull, notEmpty;</span><br><span class="line">    <span class="comment">// functions</span></span><br><span class="line">    BoundedBuffer()&#123;</span><br><span class="line">        count = <span class="number">0</span>;</span><br><span class="line">        lock = <span class="keyword">new</span> Lock();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// deposit</span></span><br><span class="line">    Deposit(c) &#123;</span><br><span class="line">        lock-&gt;Acquire();</span><br><span class="line">        <span class="keyword">while</span> (count == n)</span><br><span class="line">            notFull.Wait(&amp;lock);</span><br><span class="line">        Add c to the buffer;</span><br><span class="line">        count++;</span><br><span class="line">        notEmpty.Signal();</span><br><span class="line">        lock-&gt;Release();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// remove</span></span><br><span class="line">    Remove(c) &#123;</span><br><span class="line">        lock-&gt;Acquire();</span><br><span class="line">        <span class="keyword">while</span> (count == <span class="number">0</span>)</span><br><span class="line">            notEmpty.Wait(&amp;lock);</span><br><span class="line">        remove c from the buffer;</span><br><span class="line">        count--;</span><br><span class="line">        notFull.Signal();</span><br><span class="line">        lock-&gt;Release();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="生产者消费者问题"><a href="#生产者消费者问题" class="headerlink" title="生产者消费者问题"></a>生产者消费者问题</h4><p>信号量实现</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">semaphore mutex = <span class="number">1</span>;</span><br><span class="line">semaphore empty = n;</span><br><span class="line">semaphore full  = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">producer</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (<span class="number">1</span>) &#123;</span><br><span class="line">        iterm = produce();</span><br><span class="line">        P(empty); <span class="comment">// 请求一个空区域</span></span><br><span class="line">        P(mutex);</span><br><span class="line">        addIterm(buffer, item);</span><br><span class="line">        V(mutex);</span><br><span class="line">        V(full); <span class="comment">// 满缓冲区+1</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">consumer</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (<span class="number">1</span>) &#123;</span><br><span class="line">        P(full); <span class="comment">// 请求一个满区域</span></span><br><span class="line">        P(mutex);</span><br><span class="line">        iterm = removeIterm(buffer);</span><br><span class="line">        V(mutex);</span><br><span class="line">        V(empty); <span class="comment">// 空缓冲区+1</span></span><br><span class="line">        consumeIterm(iterm);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="存储器管理"><a href="#存储器管理" class="headerlink" title="存储器管理"></a>存储器管理</h3><ol>
<li>分区存储管理、覆盖与交换；<ul>
<li>存储管理算法<ul>
<li>首次适应：空闲分区以地址递增排序</li>
<li>最佳适应：空闲分区以容量递增排序</li>
<li>最坏适应：空闲分区以容量递减排序</li>
<li>邻近适应：同首次适应</li>
</ul>
</li>
<li>覆盖：单道程序设计中，活动分区固定在内存，非活动分区可覆盖；</li>
<li>交换：多道程序设计；如处理器调度的中级调度；被换出的进程<strong>必须</strong>处于<strong>空闲状态</strong></li>
</ul>
</li>
<li>页式管理及段式管理；</li>
<li>段页式存储管理方法及实现技术；<ul>
<li>每个进程只有一个段表，可以有多个页表。</li>
<li>段表表项：<code>|段号|页表长度|页表起始地址|</code></li>
<li>页表表项：<code>|页号|物理块号|</code></li>
</ul>
</li>
<li>虚存的原理及相关的各种算法和数据结构。</li>
</ol>
<h4 id="分区管理方式小结"><a href="#分区管理方式小结" class="headerlink" title="分区管理方式小结"></a>分区管理方式小结</h4><table>
<thead>
<tr>
<th>分区管理方式</th>
<th>内部碎片</th>
<th>外部碎片</th>
<th>硬件支持</th>
</tr>
</thead>
<tbody>
<tr>
<td>单道连续分配</td>
<td>有</td>
<td>无</td>
<td>界地址寄存器、越界检查机构</td>
</tr>
<tr>
<td>多道固定分配</td>
<td>有</td>
<td>无</td>
<td>①上下界寄存器、越界检查结构；②基地址寄存器、长度寄存器、动态地址转换机构</td>
</tr>
<tr>
<td>多道可变分配</td>
<td>无</td>
<td>有</td>
<td>同上</td>
</tr>
</tbody>
</table>
<h3 id="设备管理和磁盘调度"><a href="#设备管理和磁盘调度" class="headerlink" title="设备管理和磁盘调度"></a>设备管理和磁盘调度</h3><ol>
<li>操作系统中输入/输出功能的组织；</li>
<li>中断处理；</li>
<li>设备驱动程序、设备无关的软件接口和 <code>Spooling</code> 技术；<ul>
<li>虚拟设备是靠 <code>Spooling</code> 技术实现的；</li>
<li><code>Spooling</code> 技术将独占设备改造成共享设备；</li>
<li><code>Spooling</code> 技术的主要目的是提供主存、辅存接口；</li>
<li><code>Spooling</code> 系统由预输入程序、井管理程序和缓输出程序组成；</li>
</ul>
</li>
<li>缓冲策略；（缓冲区在内存中）<ul>
<li>单缓冲</li>
<li>双缓冲</li>
<li>循环缓冲</li>
<li>缓冲池</li>
</ul>
</li>
<li>磁盘调度算法；<ul>
<li>FCFS</li>
<li>SSTF</li>
<li>SCAN</li>
<li>C-SCAN</li>
</ul>
</li>
<li>磁盘阵列；<ul>
<li>RAID0</li>
<li>RAID1</li>
<li>RAID5</li>
<li>RAID01</li>
<li>RAID10</li>
<li>RAID50</li>
</ul>
</li>
</ol>
<h3 id="文件系统"><a href="#文件系统" class="headerlink" title="文件系统"></a>文件系统</h3><ol>
<li>文件系统特点与文件组织方式；<ul>
<li>文件组织方式：无结构文件（流式文件）、结构化文件</li>
</ul>
</li>
<li>文件系统的数据结构；<ul>
<li>文件控制块 (<code>PCB</code>) = 文件目录项</li>
<li>i-node</li>
</ul>
</li>
<li>目录的基本性质及其实现方法；<ul>
<li><code>PCB</code> 信息<ul>
<li><strong>基本信息</strong>：文件名、文件的物理位置、文件的逻辑、文件的物理结构等；</li>
<li><strong>存取控制信息</strong>：文件的存取权限等；</li>
<li><strong>使用信息</strong>：文件的建立时间、修改时间等；</li>
</ul>
</li>
</ul>
</li>
<li>磁盘空间的管理<ul>
<li>初始化：对磁盘进行低级格式化和逻辑格式化</li>
<li>引导块：存放初始化程序</li>
<li>坏块：对坏块扇区的处理</li>
</ul>
</li>
<li>分布式文件系统</li>
</ol>
<h4 id="外存分配方式小结"><a href="#外存分配方式小结" class="headerlink" title="外存分配方式小结"></a>外存分配方式小结</h4><table>
<thead>
<tr>
<th>外存分配方式</th>
<th>优点</th>
<th>缺点</th>
</tr>
</thead>
<tbody>
<tr>
<td>连续分配</td>
<td>支持顺序访问和直接访问；易于实现；存取速度快</td>
<td>会产生外部碎片；不易动态增加</td>
</tr>
<tr>
<td>链接分配</td>
<td>可以动态分配；没有外部碎片</td>
<td>只能顺序访问；可靠性差</td>
</tr>
<tr>
<td>索引分配</td>
<td>顺序访问；直接访问；查找效率高</td>
<td>索引表占空间</td>
</tr>
</tbody>
</table>
<h3 id="分布式系统"><a href="#分布式系统" class="headerlink" title="分布式系统"></a>分布式系统</h3><ol>
<li>分布式处理的特点、类型；</li>
<li>机群系统。</li>
</ol>
<h3 id="操作系统安全"><a href="#操作系统安全" class="headerlink" title="操作系统安全"></a>操作系统安全</h3><ol>
<li>操作系统安全保护目标及相关技术</li>
<li>常见操作系统攻击方法的原理和防护</li>
</ol>
<h2 id="计算机体系结构"><a href="#计算机体系结构" class="headerlink" title="计算机体系结构"></a>计算机体系结构</h2><h3 id="计算机体系结构部分考试要求"><a href="#计算机体系结构部分考试要求" class="headerlink" title="计算机体系结构部分考试要求"></a>计算机体系结构部分考试要求</h3><ul>
<li style="list-style: none"><input type="checkbox"> 掌握从外部 I/O 与上层应用交互的整体软硬件过程</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握基于 MIPS 处理器的 Linux 操作系统 TLB 例外过程</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握 C 语言与指令系统的关系</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握系统初始化时 PCI 设备的探测过程</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握 I/O 通信中 DMA 传输过程</li>
<li style="list-style: none"><input type="checkbox" checked> 能读懂 CMOS 电路，根据晶体管电路给出逻辑表达式</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握先行进位加法器结构及其 verilog 实现</li>
<li style="list-style: none"><input type="checkbox"> 掌握 Booth 编码和华莱士树</li>
<li style="list-style: none"><input type="checkbox" checked> 掌握指令流水线原理，了解解决相关的方法，能够用时空图表达流水线的运行</li>
</ul>
<h4 id="基于MIPS处理器的Linux操作系统TLB例外过程"><a href="#基于MIPS处理器的Linux操作系统TLB例外过程" class="headerlink" title="基于MIPS处理器的Linux操作系统TLB例外过程"></a>基于MIPS处理器的Linux操作系统TLB例外过程</h4><ul>
<li>TLB 例外<ul>
<li>TLB Refill: TLB 未命中时</li>
<li>TLB Invalid: TLB 命中，但V位为0；即相应物理页不在内存中</li>
<li>TLB Modify: 写 TLB 且 TLB 命中但D位为0；即非法修改只读页</li>
</ul>
</li>
<li><p>TLB Refill</p>
<ul>
<li><p><code>MIPS R4000</code> 处理器的 <code>TLB Refill</code> 程序</p>
  <figure class="highlight mips"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">.set</span> <span class="keyword">noreorder</span></span><br><span class="line"><span class="keyword">.set </span>noat</span><br><span class="line"><span class="keyword">TLBrefillR4K:</span></span><br><span class="line"><span class="keyword"> </span>   <span class="keyword">mfc0 </span><span class="built_in">k1</span>, C0_CONTEXT</span><br><span class="line">    <span class="keyword">nop</span></span><br><span class="line"><span class="keyword"> </span>   <span class="keyword">lw </span>  <span class="built_in">k0</span>, <span class="number">0</span>(<span class="built_in">k1</span>)</span><br><span class="line">    <span class="keyword">lw </span>  <span class="built_in">k1</span>, <span class="number">4</span>(<span class="built_in">k1</span>)</span><br><span class="line">    <span class="keyword">mtc0 </span><span class="built_in">k0</span>, C0_ENTRYLO0</span><br><span class="line">    <span class="keyword">mtc0 </span><span class="built_in">k1</span>, C0_ENTRYLO1</span><br><span class="line">    <span class="keyword">nop</span></span><br><span class="line"><span class="keyword"> </span>   <span class="keyword">tlbwr</span></span><br><span class="line"><span class="keyword"> </span>   <span class="keyword">eret</span></span><br><span class="line"><span class="keyword">.set </span><span class="built_in">at</span></span><br><span class="line"><span class="meta">.set</span> reorder</span><br></pre></td></tr></table></figure>
</li>
<li><p><code>MIPS</code> 处理器的 <code>Linux</code> 系统的 <code>TLB Refill</code></p>
  <figure class="highlight mips"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">mfc0 </span><span class="built_in">k0</span>, CP0_BADVADDR <span class="comment"># 取发生TLB失效的地址</span></span><br><span class="line"><span class="keyword">srl </span> <span class="built_in">k0</span>, <span class="built_in">k0</span>, <span class="number">22</span>       <span class="comment"># 最高10位是一级页表索引</span></span><br><span class="line"><span class="keyword">lw </span>  <span class="built_in">k1</span>, pgd_current  <span class="comment"># 取页表入口地址</span></span><br><span class="line"><span class="keyword">sll </span> <span class="built_in">k0</span>, <span class="built_in">k0</span>, <span class="number">2</span>        <span class="comment"># 每项 4B，左移2位得到偏移</span></span><br><span class="line"><span class="keyword">addu </span><span class="built_in">k1</span>, <span class="built_in">k1</span>, <span class="built_in">k0</span>       <span class="comment"># k1指向下一级页表入口</span></span><br><span class="line"><span class="keyword">mfc0 </span><span class="built_in">k0</span>, CP0_CONTEXT  <span class="comment"># CONTEXT包含失效的虚拟页号</span></span><br><span class="line"><span class="keyword">lw </span>  <span class="built_in">k1</span>, <span class="number">0</span>(<span class="built_in">k1</span>)        <span class="comment"># 取出第二级页表</span></span><br><span class="line"><span class="keyword">srl </span> <span class="built_in">k0</span>, <span class="built_in">k0</span>, <span class="number">1</span></span><br><span class="line"><span class="comment"># 第二级页表项每个表项管理两个物理页，每页 4B</span></span><br><span class="line"><span class="comment"># 所以偏移是按8B计算，即逻辑左移三位</span></span><br><span class="line"><span class="keyword">and </span> <span class="built_in">k0</span>, <span class="built_in">k0</span>, <span class="number">0xff8</span>    <span class="comment"># 算出第二级页表的偏移</span></span><br><span class="line"><span class="keyword">addu </span><span class="built_in">k1</span>, <span class="built_in">k1</span>, <span class="built_in">k0</span>       <span class="comment"># k1为最终表项的地址</span></span><br><span class="line"><span class="keyword">lw </span>  <span class="built_in">k0</span>, <span class="number">0</span>(<span class="built_in">k1</span>)        <span class="comment"># 成对存放，一个偶数页</span></span><br><span class="line"><span class="keyword">lw </span>  <span class="built_in">k1</span>, <span class="number">4</span>(<span class="built_in">k1</span>)        <span class="comment"># 奇数页</span></span><br><span class="line"><span class="keyword">srl </span> <span class="built_in">k0</span>, <span class="built_in">k0</span>, <span class="number">6</span>        <span class="comment"># 移除6位exts</span></span><br><span class="line"><span class="keyword">mtc0 </span><span class="built_in">k0</span>, CP0_ENTRYLO0 <span class="comment"># 写入偶数页表项</span></span><br><span class="line"><span class="keyword">srl </span> <span class="built_in">k1</span>, <span class="built_in">k1</span>, <span class="number">6</span></span><br><span class="line"><span class="keyword">mtc0 </span><span class="built_in">k1</span>, CP0_ENTRYLO1 <span class="comment"># 写入奇数页表项</span></span><br><span class="line"><span class="keyword">tlbwr </span>                <span class="comment"># 随机写入TLB表项</span></span><br><span class="line"><span class="keyword">eret </span>                 <span class="comment"># 异常返回</span></span><br></pre></td></tr></table></figure>
</li>
<li><p><code>MIPS</code> 架构下 <code>Linux</code> 系统 <code>TLB Exception</code> 伪代码</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"># TLB refill</span><br><span class="line">TLB refill exception(0x80000000):</span><br><span class="line">    get badvaddr, pgd;</span><br><span class="line">    pte_table ptr = badvaddr&gt;&gt;2&lt;2 + pgd;</span><br><span class="line">    get context, offset = context&gt;&gt;1 &amp; 0xff8;</span><br><span class="line">    load offset(ptr), (offset+4)(ptr);</span><br><span class="line">    right shift 6 bits, write to entrylo[0:1];</span><br><span class="line">    tlbwr;</span><br><span class="line"># TLB modify</span><br><span class="line">TLB modified exception(0x800000180:handle_mod):</span><br><span class="line">    load pte;</span><br><span class="line">    if(__PAGE_WRITE set, set ACCESSED|MODIFIED|VALID|DIRTY)</span><br><span class="line">        reload tlb, tlbwi;</span><br><span class="line">    else</span><br><span class="line">        DO_FAULT(1);</span><br><span class="line"># TLB load</span><br><span class="line">TLB load exception(0x80000180:handle_tlbl):</span><br><span class="line">    load pte;</span><br><span class="line">    if(__PAGE_PRESENT &amp;&amp; _PAGE_READ)</span><br><span class="line">        set ACCESSED|VALID;</span><br><span class="line">    else</span><br><span class="line">        DO_FAULT(0);</span><br><span class="line"># TLB store</span><br><span class="line">TLB store exception(0x80000180:handle_tlbs):</span><br><span class="line">    load pte;</span><br><span class="line">    if(__PAGE_PRESENT &amp;&amp; _PAGE_WRITE)</span><br><span class="line">        set ACCESSED|VALID|MODIFIED|DIRTY;</span><br><span class="line">    else</span><br><span class="line">        DO_FAULT(1);</span><br></pre></td></tr></table></figure>
</li>
</ul>
</li>
</ul>
<h4 id="I-O通信中DMA传输过程"><a href="#I-O通信中DMA传输过程" class="headerlink" title="I/O通信中DMA传输过程"></a>I/O通信中DMA传输过程</h4><ol>
<li>处理器为 DMA 请求预先分配一段地址空间；</li>
<li>处理器设置 DMA 控制器参数。<ul>
<li>设备标识</li>
<li>数据传送的方向 (内存 → 硬盘 or 硬盘 → 内存)</li>
<li>内存中用于数据传送的源地址或目标地址</li>
<li>传输的字节数量</li>
<li>简而言之，就是明确数据的<strong>我是谁、从哪来、要去哪儿、我要干嘛、我有几个伙伴要一起走</strong></li>
</ul>
</li>
<li>DMA 控制器进行数据传输。</li>
<li>DMA 控制器向处理器发出一个中断，通知处理器数据传送的结果（成功或者出错以及错误信息）。</li>
<li>处理器完成本次 DMA 请求，可以开始新的 DMA 请求。</li>
</ol>
<h4 id="系统初始化时PCI设备的探测过程"><a href="#系统初始化时PCI设备的探测过程" class="headerlink" title="系统初始化时PCI设备的探测过程"></a>系统初始化时PCI设备的探测过程</h4><ol>
<li>将初始总线号、初始设备号、初始功能号设为0；</li>
<li>使用当前的总线号、设备号、功能号组成一个配置空间地址；使用该地址，访问其0号寄存器，检查其设备号；</li>
<li>如果读出全为1或全0，表示没有设备；</li>
<li>如果该设备为有效设备，检查每个BAR所需空间大小，并收集相关信息；</li>
<li>检测其是否为多功能设备，如果是则将功能号加1重复扫描，执行第2步；</li>
<li>如果该设备为桥设备，则给该桥配置一个新的总线号，再使用该总线号，从设备号0、功能号0开始递归调用，执行第2步；</li>
<li>如果设备号非31，则设备号加1，继续执行第2步；如果设备号为31，且总线号为0，表示扫描结束；如果总线号非0，则退回上一层递归调用。</li>
</ol>
<h4 id="先行进位加法器结构及其verilog实现"><a href="#先行进位加法器结构及其verilog实现" class="headerlink" title="先行进位加法器结构及其verilog实现"></a>先行进位加法器结构及其verilog实现</h4><ol>
<li>并行进位逻辑<ul>
<li>$c_{i+1} = a_i \And b_i | a_i \And c_i | b_i \And c_i = g_i | p_i \And c_i$</li>
</ul>
</li>
<li>Verilog实现 <figure class="highlight verilog"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 先行进位4位加法器</span></span><br><span class="line"><span class="keyword">module</span> adder_4(</span><br><span class="line">    <span class="keyword">input</span>  [<span class="number">3</span>:<span class="number">0</span>] a,</span><br><span class="line">    <span class="keyword">input</span>  [<span class="number">3</span>:<span class="number">0</span>] b,</span><br><span class="line">    <span class="keyword">input</span>        cin,</span><br><span class="line">    <span class="keyword">output</span> [<span class="number">3</span>:<span class="number">0</span>] cout</span><br><span class="line">);</span><br><span class="line">    <span class="keyword">wire</span> [<span class="number">3</span>:<span class="number">0</span>] p,g;</span><br><span class="line">    <span class="comment">// generate pi and gi</span></span><br><span class="line">    <span class="keyword">generate</span></span><br><span class="line">        <span class="keyword">genvar</span> i;</span><br><span class="line">        <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; <span class="number">4</span>; i++) <span class="keyword">begin</span></span><br><span class="line">            <span class="keyword">assign</span> p[i] = a[i] | b[i];</span><br><span class="line">            <span class="keyword">assign</span> g[i] = a[i] &amp; b[i];</span><br><span class="line">        <span class="keyword">end</span></span><br><span class="line">    <span class="keyword">endgenerate</span></span><br><span class="line">    <span class="comment">// generate cout</span></span><br><span class="line">    cout[<span class="number">0</span>] = g[<span class="number">0</span>] | p[<span class="number">0</span>] &amp; cin;</span><br><span class="line">    cout[<span class="number">1</span>] = g[<span class="number">1</span>] | p[<span class="number">1</span>] &amp; cout[<span class="number">0</span>];</span><br><span class="line">    cout[<span class="number">2</span>] = g[<span class="number">2</span>] | p[<span class="number">2</span>] &amp; cout[<span class="number">1</span>];</span><br><span class="line">    cout[<span class="number">3</span>] = g[<span class="number">3</span>] | p[<span class="number">3</span>] &amp; cout[<span class="number">2</span>];</span><br><span class="line"><span class="keyword">endmodule</span></span><br></pre></td></tr></table></figure>
</li>
</ol>
<h3 id="计算机体系结构概论"><a href="#计算机体系结构概论" class="headerlink" title="计算机体系结构概论"></a>计算机体系结构概论</h3><ol>
<li>计算机体系结构的发展</li>
<li>计算机系统层次结构<ul>
<li>计算机系统的基本组成，计算机硬件的基本组成，计算机软件和硬件的关系，计算机的工作过程</li>
</ul>
</li>
<li>衡量计算机的指标</li>
<li>计算机体系结构的设计原则</li>
</ol>
<p>设 l 为曲线 $y = \sin x$ 从 x = 0 到 x = π 的有向弧线段，则 $I = \int_l \sqrt{x^2+y^2+1} dx + y[xy+\ln (x+\sqrt{x^2+y^2+1})]dy$ = ？</p>
<p>$\iint y^2 dxdy = \int <em>0^{\pi} dx \int</em>{0}^{\sin x} y^2 dy = \dfrac{1}{3}\int_{0}^{\pi} \sin^3x dx$</p>
<h3 id="指令系统结构"><a href="#指令系统结构" class="headerlink" title="指令系统结构"></a>指令系统结构</h3><ol>
<li>指令系统设计原则</li>
</ol>
<h4 id="指令系统的演变"><a href="#指令系统的演变" class="headerlink" title="指令系统的演变"></a>指令系统的演变</h4><ul>
<li>指令集分类<ul>
<li>精简指令集 (RISC)</li>
<li>复杂指令集 (CISC)</li>
<li>超长指令字 (VLIW)</li>
</ul>
</li>
<li>存储管理<ul>
<li>段式</li>
<li>页式</li>
<li>段页式</li>
</ul>
</li>
<li>运行级别<ul>
<li>MIPS<ul>
<li>调试模式</li>
<li>根-核心模式、根-监管模式、根-用户模式、</li>
<li>客户监管模式、客户-用户模式、客户-监管模式</li>
</ul>
</li>
</ul>
</li>
</ul>
<h4 id="指令集结构"><a href="#指令集结构" class="headerlink" title="指令集结构"></a>指令集结构</h4><ul>
<li>指令集的分类<ul>
<li>功能分类：<ul>
<li>算术与逻辑运算、转移、访存、系统指令等特殊指令</li>
</ul>
</li>
<li>指令使用数据的方式<ul>
<li>堆栈型、寄存器型、寄存器-存储器型、寄存器-寄存器型</li>
</ul>
</li>
</ul>
</li>
<li>指令操作数的存储指令</li>
<li>操作数的特征</li>
<li>指令操作和编码</li>
<li>C 语言的机器表示</li>
</ul>
<h4 id="异常与中断"><a href="#异常与中断" class="headerlink" title="异常与中断"></a>异常与中断</h4><ul>
<li>异常分类<ul>
<li>外部事件，即<strong>中断</strong></li>
<li>指令执行中产生的错误：除零操作、指令不存在、地址不对齐、非法地址空间访问等</li>
<li>地址转换异常</li>
<li>系统调用和陷入</li>
<li>需要软件修复的运算</li>
<li>数据完整性问题</li>
</ul>
</li>
<li><p>异常处理</p>
<ol>
<li>异常处理准备<ul>
<li>精确异常：被 <code>Exception</code> 打断的指令之前的指令都正常执行，之后的指令都不执行。</li>
</ul>
</li>
<li>确定异常来源</li>
<li>保存执行状态</li>
<li>处理异常</li>
<li><p>恢复执行状态并返回</p>
<figure class="highlight mips"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># example of exception handler</span></span><br><span class="line"><span class="symbol">Exception:</span></span><br><span class="line">    SAVE    <span class="comment"># micro save context</span></span><br><span class="line">    <span class="keyword">jal </span>IRQ_Exception</span><br><span class="line">    RESTORE <span class="comment"># micro restore context</span></span><br><span class="line">    <span class="keyword">eret</span></span><br><span class="line"><span class="keyword"> </span>   <span class="keyword">nop</span></span><br></pre></td></tr></table></figure>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// example of IRQ_Exception</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">IRQ_Exception</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">int</span> cp0cause;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">int</span> int_num;</span><br><span class="line">    __<span class="function">asm__ <span class="title">volatile</span><span class="params">(</span></span></span><br><span class="line"><span class="function"><span class="params">        <span class="string">"mfc0 %0, $13"</span></span></span></span><br><span class="line"><span class="function"><span class="params">        : <span class="string">"=r"</span>(cp0cause)</span></span></span><br><span class="line">    ); // get the value of CP0_CAUSE Register</span><br><span class="line">    <span class="keyword">for</span> (int_num = <span class="number">0</span>; int_num &lt; <span class="number">8</span>; int_num++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (cp0cause&gt;&gt;(int_num+<span class="number">8</span>) &amp; <span class="number">0x1</span>) &#123;</span><br><span class="line">            Irq_hander[int_num]();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>
</li>
<li><p>中断传递机制</p>
<ul>
<li>中断线<ul>
<li>中断源直接与 CPU 引脚相连</li>
<li>不易扩展，且低效</li>
</ul>
</li>
<li>消息传递机制<ul>
<li>以数据方式在<strong>总线</strong>上传输，向固定内存地址写一个数；</li>
<li>方便扩展和管理</li>
</ul>
</li>
</ul>
</li>
</ul>
<h4 id="存储管理"><a href="#存储管理" class="headerlink" title="存储管理"></a>存储管理</h4><p><code>MIPS</code> 处理器对虚存系统的支持，<code>Linux</code> 操作系统的存储管理。</p>
<h3 id="计算机硬件结构"><a href="#计算机硬件结构" class="headerlink" title="计算机硬件结构"></a>计算机硬件结构</h3><ol>
<li>计算机组成原理和结构<br> 冯诺依曼结构，计算机硬件结构的演进，处理器与 I/O 间的通信，计算机系统主要组成部件</li>
<li>计算机总线接口技术<br> 片上总线，内存总线，I/O 总线</li>
<li>计算机系统启动过程<br> 处理器核初始化，总线接口初始化，设备探测及驱动加载</li>
</ol>
<h4 id="系统复位到操作系统启动的简要流程图"><a href="#系统复位到操作系统启动的简要流程图" class="headerlink" title="系统复位到操作系统启动的简要流程图"></a>系统复位到操作系统启动的简要流程图</h4><ul>
<li>系统复位到操作系统启动的简要流程图<br>  <img src="/images/201811/cpu_inititalization.png" alt="系统复位到操作系统启动的简要流程图"></li>
</ul>
<h4 id="设备探测及驱动加载"><a href="#设备探测及驱动加载" class="headerlink" title="设备探测及驱动加载"></a>设备探测及驱动加载</h4><ul>
<li>PCI 协议下 I/O 的系统空间被分为三部分：配置空间、IO 空间和 Memory 空间。</li>
</ul>
<h3 id="cpu微结构"><a href="#cpu微结构" class="headerlink" title="cpu微结构"></a>cpu微结构</h3><ol>
<li>二进制与逻辑电路<br> 计算机中数的表示，CMOS 逻辑电路</li>
<li>简单运算器设计<br> 定点补码加法，减法，比较，移位</li>
<li>定点补码乘法器</li>
<li>指令流水线<br> 处理器数据通路，五级流水处理器，解决指令相关</li>
</ol>

      
    </div>

    

    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/2019考研/" rel="tag"># 2019考研</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/11/20/kaoyan-politcs/" rel="next" title="考研政治">
                <i class="fa fa-chevron-left"></i> 考研政治
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/12/03/next-custom-fonts/" rel="prev" title="NexT 主题自定义字体">
                NexT 主题自定义字体 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
      <div id="sidebar-dimmer"></div>
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.gif"
                alt="Wu Jiahao ♡" />
            
              <p class="site-author-name" itemprop="name">Wu Jiahao ♡</p>
              <p class="site-description motion-element" itemprop="description">Stay hungry, stay foolish.</p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">9</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/categories/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">4</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/tags/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">8</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          

          
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#目录"><span class="nav-number">1.</span> <span class="nav-text">目录</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#数据结构"><span class="nav-number">2.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#数据结构考试要求"><span class="nav-number">2.1.</span> <span class="nav-text">数据结构考试要求</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#绪论"><span class="nav-number">2.2.</span> <span class="nav-text">绪论</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线性表"><span class="nav-number">2.3.</span> <span class="nav-text">线性表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#堆栈与队列"><span class="nav-number">2.4.</span> <span class="nav-text">堆栈与队列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组和广义表"><span class="nav-number">2.5.</span> <span class="nav-text">数组和广义表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#树与二叉树"><span class="nav-number">2.6.</span> <span class="nav-text">树与二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#图"><span class="nav-number">2.7.</span> <span class="nav-text">图</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#关键路径"><span class="nav-number">2.7.1.</span> <span class="nav-text">关键路径</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#查找"><span class="nav-number">2.8.</span> <span class="nav-text">查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#排序"><span class="nav-number">2.9.</span> <span class="nav-text">排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#操作系统"><span class="nav-number">3.</span> <span class="nav-text">操作系统</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#操作系统考试要求"><span class="nav-number">3.1.</span> <span class="nav-text">操作系统考试要求</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#操作系统概述"><span class="nav-number">3.2.</span> <span class="nav-text">操作系统概述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程"><span class="nav-number">3.3.</span> <span class="nav-text">进程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线程、对称多处理smp和微内核"><span class="nav-number">3.4.</span> <span class="nav-text">线程、对称多处理smp和微内核</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#处理器调度"><span class="nav-number">3.5.</span> <span class="nav-text">处理器调度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#并发性"><span class="nav-number">3.6.</span> <span class="nav-text">并发性</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#软件实现互斥小结"><span class="nav-number">3.6.1.</span> <span class="nav-text">软件实现互斥小结</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#管程小结"><span class="nav-number">3.6.2.</span> <span class="nav-text">管程小结</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#生产者消费者问题"><span class="nav-number">3.6.3.</span> <span class="nav-text">生产者消费者问题</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#存储器管理"><span class="nav-number">3.7.</span> <span class="nav-text">存储器管理</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#分区管理方式小结"><span class="nav-number">3.7.1.</span> <span class="nav-text">分区管理方式小结</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#设备管理和磁盘调度"><span class="nav-number">3.8.</span> <span class="nav-text">设备管理和磁盘调度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#文件系统"><span class="nav-number">3.9.</span> <span class="nav-text">文件系统</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#外存分配方式小结"><span class="nav-number">3.9.1.</span> <span class="nav-text">外存分配方式小结</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分布式系统"><span class="nav-number">3.10.</span> <span class="nav-text">分布式系统</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#操作系统安全"><span class="nav-number">3.11.</span> <span class="nav-text">操作系统安全</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#计算机体系结构"><span class="nav-number">4.</span> <span class="nav-text">计算机体系结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#计算机体系结构部分考试要求"><span class="nav-number">4.1.</span> <span class="nav-text">计算机体系结构部分考试要求</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#基于MIPS处理器的Linux操作系统TLB例外过程"><span class="nav-number">4.1.1.</span> <span class="nav-text">基于MIPS处理器的Linux操作系统TLB例外过程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#I-O通信中DMA传输过程"><span class="nav-number">4.1.2.</span> <span class="nav-text">I/O通信中DMA传输过程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#系统初始化时PCI设备的探测过程"><span class="nav-number">4.1.3.</span> <span class="nav-text">系统初始化时PCI设备的探测过程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#先行进位加法器结构及其verilog实现"><span class="nav-number">4.1.4.</span> <span class="nav-text">先行进位加法器结构及其verilog实现</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#计算机体系结构概论"><span class="nav-number">4.2.</span> <span class="nav-text">计算机体系结构概论</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#指令系统结构"><span class="nav-number">4.3.</span> <span class="nav-text">指令系统结构</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#指令系统的演变"><span class="nav-number">4.3.1.</span> <span class="nav-text">指令系统的演变</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#指令集结构"><span class="nav-number">4.3.2.</span> <span class="nav-text">指令集结构</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#异常与中断"><span class="nav-number">4.3.3.</span> <span class="nav-text">异常与中断</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#存储管理"><span class="nav-number">4.3.4.</span> <span class="nav-text">存储管理</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#计算机硬件结构"><span class="nav-number">4.4.</span> <span class="nav-text">计算机硬件结构</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#系统复位到操作系统启动的简要流程图"><span class="nav-number">4.4.1.</span> <span class="nav-text">系统复位到操作系统启动的简要流程图</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#设备探测及驱动加载"><span class="nav-number">4.4.2.</span> <span class="nav-text">设备探测及驱动加载</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#cpu微结构"><span class="nav-number">4.5.</span> <span class="nav-text">cpu微结构</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Wu Jiahao ♡</span>

  

  
</div>




  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动 v3.7.1</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 – <a class="theme-link" target="_blank" href="https://theme-next.org">NexT.Mist</a> v6.3.0</div>




        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
	
    

    
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>
























  



  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/reading_progress/reading_progress.js"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=6.3.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=6.3.0"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=6.3.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=6.3.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=6.3.0"></script>



  



  










  





  

  

  

  
  

  
  

  
    
      <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      },
      TeX: {equationNumbers: { autoNumber: "AMS" }}
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

    
  


  
  

  

  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=6.3.0"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=6.3.0"></script>


  

  

  
  <style>
    .copy-btn {
      display: inline-block;
      padding: 6px 12px;
      font-size: 13px;
      font-weight: 700;
      line-height: 20px;
      color: #333;
      white-space: nowrap;
      vertical-align: middle;
      cursor: pointer;
      background-color: #eee;
      background-image: linear-gradient(#fcfcfc, #eee);
      border: 1px solid #d5d5d5;
      border-radius: 3px;
      user-select: none;
      outline: 0;
    }

    .highlight-wrap .copy-btn {
      transition: opacity .3s ease-in-out;
      opacity: 0;
      padding: 2px 6px;
      position: absolute;
      right: 4px;
      top: 8px;
    }

    .highlight-wrap:hover .copy-btn,
    .highlight-wrap .copy-btn:focus {
      opacity: 1
    }

    .highlight-wrap {
      position: relative;
    }
  </style>
  <script>
    $('.highlight').each(function (i, e) {
      var $wrap = $('<div>').addClass('highlight-wrap')
      $(e).after($wrap)
      $wrap.append($('<button>').addClass('copy-btn').append('复制').on('click', function (e) {
        var code = $(this).parent().find('.code').find('.line').map(function (i, e) {
          return $(e).text()
        }).toArray().join('\n')
        var ta = document.createElement('textarea')
        document.body.appendChild(ta)
        ta.style.position = 'absolute'
        ta.style.top = '0px'
        ta.style.left = '0px'
        ta.value = code
        ta.select()
        ta.focus()
        var result = document.execCommand('copy')
        document.body.removeChild(ta)
        
          if(result)$(this).text('复制成功')
          else $(this).text('复制失败')
        
        $(this).blur()
      })).on('mouseleave', function (e) {
        var $b = $(this).find('.copy-btn')
        setTimeout(function () {
          $b.text('复制')
        }, 300)
      }).append(e)
    })
  </script>


</body>
</html>
